﻿#include"Heap.h"

//扩容
void Dalation(Heap* hp)
{
	assert(hp != NULL);
	HPDataType* temp = (HPDataType*)realloc(hp->a, 2 * hp->capacity * sizeof(HPDataType));
	if (temp == NULL)
	{
		perror("realloc fail!");
		exit(-1);
	}
	hp->a = temp;
	hp->capacity = hp->capacity * 2;
}

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp != NULL);
	HPDataType* temp = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (temp == NULL)
	{
		perror("malloc fail!");
		exit(-1);
	}
	hp->a = temp;
	hp->capacity = 4;
	hp->size = 0;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp != NULL);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

//交换
void swap(HPDataType* arr, int x, int y)
{
	HPDataType temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}

//向上调整
void Adjustup(Heap* hp)
{
	int child = hp->size;
	int parent = (child - 1) / 2;
	while (hp->a[parent] > hp->a[child] && parent >= 0)
	{
		swap(hp->a, parent, child);
		child = parent;
		parent = (child - 1) / 2;
	}
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp != NULL);
	if (hp->capacity == hp->size)
	{
		Dalation(hp);
	}
	hp->a[hp->size] = x;
	if (hp->size != 0)
	{
		Adjustup(hp);
	}
	hp->size++;
}

//向下调整
void Adjustdown(Heap* hp)
{
	int parent = 0;
	int child = parent * 2 + 1;
	while (hp->a[parent] > hp->a[child] && child < hp->size)
	{
		if (hp->a[child] > hp->a[child + 1] && child + 1 < hp->size)
		{
			child++;
		}
		swap(hp->a, parent, child);
		parent = child;
		child = parent * 2 + 1;
	}
}

// 堆的删除(出堆顶)
void HeapPop(Heap* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	swap(hp->a, 0, hp->size - 1);
	hp->size--;
	Adjustdown(hp);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp != NULL);
	return hp->size;
}

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp != NULL);
	if (hp->size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}